Search results for "Large neighborhood search"
showing 5 items of 5 documents
Routing electric vehicles with a single recharge per route
2020
Networks : an international journal (2020). doi:10.1002/net.21964
Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem
2019
In the dial-a-ride problem, user-specified transport requests from origin to destination points have to be served by a fleet of homogeneous vehicles. The problem variant we consider aims at finding a set of minimum-cost routes satisfying constraints on vehicle capacity, time windows, maximum route duration, and maximum user ride times. We propose an adaptive large neighborhood search (ALNS) for its solution. The key novelty of the approach is an exact amortized constant-time algorithm for evaluating the feasibility of request insertions in the repair steps of the ALNS. In addition, we use two optional improvement techniques: a local-search-based intraroute improvement of routes of promisin…
Hybridizing large neighborhood search and exact methods for generalized vehicle routing problems with time windows
2021
International audience; Delivery options are at the heart of the generalized vehicle routing problem with time windows (GVRPTW) allowing that customer requests are shipped to alternative delivery locations which can also have different time windows. Recently, the vehicle routing problem with delivery options was introduced into the scientific literature. It extends the GVRPTW by capacities of shared locations and by specifying service-level constraints defined by the customers' preferences for delivery options. The vehicle routing problem with delivery options also generalizes the vehicle routing problem with home roaming delivery locations and the vehicle routing problem with multiple time…
The Heterogeneous Fleet Vehicle Routing Problem with Draft Limits
2023
Over the past two decades, international maritime transport has been characterized by the advent of ever larger ships. This phenomenon is known as naval gigantism. If, on the one hand, naval gigantism allows to reduce transport costs by exploiting the economies of scale achievable by large ships, on the other hand, it implies a series of operational issues. Indeed, due to their large draft, such giant vessels are not allowed to enter small ports when fully or near-fully loaded, and in some cases, they cannot enter such small ports at all. In fact, their draft can strongly vary depending on the load on board. This implies restrictions for vessels in accessing ports, which impact not only at …
Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier
2019
Abstract The vehicle-routing problem with private fleet and common carrier (VRPPC) extends the capacitated VRP by considering the option of outsourcing customers to subcontractors at a customer-dependent cost instead of serving them with the private fleet. The VRPPC has important applications in small package shipping and manufacturing, but despite its relevance, no exact solution approach has been introduced so far. We propose a branch-price-and-cut algorithm that is able to solve small to medium-sized instances and provides tight lower bounds for larger instances from the literature. In addition, we develop a large neighborhood search that shows a decent solution quality and competitive r…